import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public int numberOfArithmeticSlices(int[] nums) {
        int n = nums.length;
        Map<Long, List<Integer>> map = new HashMap<>();
        map.put((long)nums[0], new ArrayList<Integer>());
        map.get((long)nums[0]).add(0);
        int[][] dp = new int[n][n]; // 以 i j 为结尾的子序列中等差序列的个数
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                dp[i][j] = 0;
            }
        }
        int ret = 0;
        for(int i = 1; i < n; i++){
            for(int j = i + 1; j < n; j++){
                long num = 2 * (long)nums[i] - (long)nums[j];
                if(map.get(num) != null){
                    for(int x : map.get(num)){
                        dp[i][j] += (dp[x][i] + 1);
                    }
                }
                ret += dp[i][j];
            }
            if(map.get((long)nums[i]) == null) map.put((long)nums[i], new ArrayList<Integer>());
            map.get((long)nums[i]).add(i);
        }
        return ret;
    }
}